package com.zm.demo.core.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class MyStack {

    Queue<Integer> queue = new LinkedBlockingQueue<>();
    Queue<Integer> queue1 = new LinkedBlockingQueue<>();
    int count=0;
    /** Initialize your data structure here. */
    public MyStack() {

    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        count++;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {

        for (int i = 0; i < count-1; i++) {
            queue1.add(queue.poll());
        }
        int r = queue.poll();
        for (int i = 0; i < count-1; i++) {
            queue.add(queue1.poll());
        }
        count--;
        return r;
    }
    
    /** Get the top element. */
    public int top() {
        for (int i = 0; i < count-1; i++) {
            queue1.add(queue.poll());
        }
        int r = queue.poll();
        queue.add(r);
        for (int i = 0; i < count-1; i++) {
            queue.add(queue1.poll());
        }
        return r;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return count == 0;
    }


    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || pushed.length == 0){
            return true;
        }
        int length = pushed.length;
        Stack<Integer>s = new Stack<>();
        for(int i = 0, j = 0; j < length; ){
            if(i == length){
                if(s.size()>0){
                    if(s.pop() != popped[j++]){
                        return false;
                    }
                }
            }else if(pushed[i] == popped[j]){
                i++;
                j++;
            }else{
                if (s.size() > 0 && s.peek() == popped[j]){
                    s.pop();
                    j++;
                }else{
                    s.push(pushed[i++]);
                }
            }

        }
        return true;
    }
}
